// https://leetcode.cn/problems/distinct-subsequences/
// Created by ade on 2022/7/20.
//
#include <iostream>
#include <string>
#include <map>
#include <vector>


using namespace std;

class Solution {
public:
    // string a = "rabbbit";
    // string b = "rabbit";
    /*
     * r[1,10,11,13]
     * a[2,3,9]
     * b[4,5,7]
     * b[4,5,7]
     * i[15,17,19]
     * t[16,18,20]
     * */
    // 会超时，基本的思路是：先找出t字符串中每个字符对应的索引，如上注释，后面就是广度搜索出所有的组合

    // dfs超时
    int sum = 0;
    vector <vector<int>> myVec;
    int height = 0;

    int numDistinct1(string s, string t) {
        height = t.size();
        map<char, vector<int>> myMap = {};
        for (int j = 0; j < s.size(); j++) {
            if (t.find(s[j]) != string::npos) {
                myMap[s[j]].push_back(j);
            }
        }
        for (int i = 0; i < t.size(); i++) {
            if (myMap[t[i]].empty()) return 0;
            myVec.push_back(myMap[t[i]]);
        }
        dfs(0, -1);
        return sum;
    }

    void dfs(int index, int lastIndex) {
        if (index == height) {
            sum++;
            return;
        }
        for (int i = 0; i < myVec[index].size(); i++) {
            if (myVec[index][i] <= lastIndex) continue;
            dfs(index + 1, myVec[index][i]);
        }
    }

    // 动态规划
    int numDistinct(string s, string t) {
        int sLen = s.size();
        int tLen = t.size();
        unsigned long long dp[sLen + 1][tLen + 1];
        for (int j = 0; j <= tLen; j++) {
            dp[0][j] = 0;
        }
        for (int i = 0; i <= sLen; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= tLen; j++) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[sLen][tLen];
    }


};

int main() {
    string a = "adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc";
    string b = "bcddceeeebecbc";
    Solution so;
    auto res = so.numDistinct(a, b);
    cout << res << endl;
    return 0;
}